package com.zjsru.oneDay;

/**
 * 消除游戏
 * <p>
 * 输入：n = 9
 * 输出：6
 * 解释：
 * arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
 * arr = [2, 4, 6, 8]
 * arr = [2, 6]
 * arr = [6]
 */
public class lastRemaining {
    public int lastRemaining(int n) {
//        //约瑟夫环解法
//        return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2));

//        如果k是奇数则删除左边的，如果k是偶数则删除右边的
        int a1 = 1;
        int cnt = n, k = 0, step = 1;
        while (cnt > 1) {
            if (k % 2 == 0) {
                //正向
                a1 = step + a1;
            } else {
                a1 = (cnt % 2 == 0) ? a1 : a1 + step;
            }
            k++;
            step = step << 1;
            cnt = cnt >> 1;//n>>1：移位操作，删除n二进制的最右一位。
        }
        return a1;
    }

    public static void main(String[] args) {
        lastRemaining lastRemaining = new lastRemaining();
        int n = 9;
        System.out.println(lastRemaining.lastRemaining(n));
    }
}
